1327F - AND Segments - CodeForces Solution

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define x first
#define y second
#define vi vector<int>
#define vpi vector<pii>
#define all(x) (x).begin(),(x).end()
#define WT int TT=read();while(TT--)
using namespace std;

inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
inline void ckmax(int &a,int b){a=(a>b?a:b);}
inline void ckmin(int &a,int b){a=(a<b?a:b);}

const int Mod=998244353;
const int M=5e5+10;
int n,k,m,l[M],r[M],x[M],c[M],dp[M],ans=1;
vi e[M];

signed main()
{
	n=read(),k=read(),m=read();
	for (int i=1;i<=n;i++)e[i].clear();
	for (int i=1;i<=m;i++)l[i]=read(),r[i]=read(),x[i]=read(),e[r[i]].pb(i);
	for (int w=0;w<k;w++)
	{
		for (int i=1;i<=n;i++)c[i]=0;
		for (int i=1;i<=m;i++)
			if (x[i]>>w&1)c[l[i]]++,c[r[i]+1]--;
		for (int i=1;i<=n;i++)c[i]+=c[i-1],dp[i]=0;
		int pos=-1,S=1;dp[0]=1;
		for (int i=1;i<=n;i++)
		{
			if (c[i]==0)
				dp[i]=S,S=S*2%Mod;
			for (auto id:e[i])
			{
				if (x[id]>>w&1)continue;
				while(pos+1<l[id])pos++,S=(S-dp[pos]+Mod)%Mod,dp[pos]=0;
			}
		}
//		cerr<<S<<'\n';
		ans=ans*S%Mod;
	}
	cout<<ans<<'\n';
	return 0;
}